\documentclass[11pt, onecolumn, a4paper]{article}
\usepackage{latexsym}
% \usepackage[dvips]{graphicx}
\usepackage[pdftex]{graphicx}
\DeclareGraphicsExtensions{.pdf}
% Use UTF for character encoding
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\addtolength{\voffset}{-1.5cm}
\addtolength{\textheight}{1cm}
\addtolength{\textwidth}{1.5cm}
\addtolength{\marginparwidth}{-1.5cm}
\author{
Alessandro Stranieri\\
Dip. di Elettronica e Informazione\\
Politecnico di Milano\\
alessandro.stranieri@mail.polimi.it \and
Nicolas Tagliani\\
Dip. di Elettronica e Informazione\\
Politecnico di Milano\\
nicolas.tagliani@mail.polimi.it }
\title{B Smart\\Behavioural sequence modeler and recognition tool}
\date{}
\begin{document}
\maketitle \tableofcontents \newpage

\abstract{}
In questo documento viene descritto il lavoro di sviluppo di un framework
destinato alla modellizazione e al riconoscimento di sequenze di simboli
appartenenti ad un alfabeto arbitrario tramite hidden markov models (HMMs). Tali
sequenze possono essere pensate come sequenze di azioni realizzate da un
generico agente, cioè come manifestazione di un comportamento.

Questo framework trova la sua collocazione in tutti quegli ambiti in cui si
desidera apprendere e classificare modelli di comportamento, ma si ignorano i
dettagli di tali processi e gli unici dati di cui si dispone sono le osservazioni
che li descrivono.


\section{Introduzione}
Il framework presentato in questo documento è stato svolto inerentemente al
Laboratorio di Intelligenza Artificiale e Robotica presso il Politecnico di
Milano. L'idea generale alla base del progetto, è quella di poter rendere
disponibile uno strumento che permetta di manipolare modelli comportamentali.

\subsection{Modelli Comportamentali}

I processi che hanno luogo nel mondo reale producono in genere delle sequenze di
eventi osservabili \cite{rabiner}. Di questi processi può essere di un qualche
interesse produrre un modello. In questo contesto si intende per comportamento
una sequenza di azioni prodotte da un generico agente. Dal momento che le azioni
che compogno il comportamento costituiscono ciò che si può osservare di esso,
nulla vieta di assimililare un comportamento ad un processo, un fenomeno,
che produce osservazioni. Alla base di questo progetto vi è l'intenzione di
investigare la possibilità di creare e utilizzare modelli comportamentali ovvero
modelli che riproducano le caratteristiche di un comportamento che sono di un certo interesse. La disponibilità del modello di un fenomeno in generale porta due
tipi di vantaggi:

\begin{enumerate}
\item Il fenomeno può essere replicato e reingegnerizzato, eventualmente tralasciando aspetti di esso che non interessano nell'applicazione.
\item Si possono fare delle predizioni e prendere decisioni riguardo l'evoluzione prossima di tale fenomeno.
\end{enumerate}

Meccanismi che apprendano e replichino comportamenti possono trovare applicazione
in ambiti diversi, presumibilmente con successo se pensati come
\hyphenation{so-lu-zio-ne}soluzione più flessibile rispetto a sistemi basati su
regole rigide. Ad esempio modelli comportamentali appresi dall'andamento del mercato
possono essere utilizzati ad per fare previsioni in campo economico oppure la
possibilità di riconoscere un determinato comportamento, perchè aderente ad un
certo modello, potrebbe essere di estrema utilità nella realizzazione di sistemi
di sicurezza dove si potrebbero classificare e riconoscere comportamenti dannosi
o meno nei confronti del nostro sistema.

\newpage
\subsection{Specifiche di progetto}

Di seguito riportiamo le specifiche di progetto. 

Poiché processi diversi producono osservazioni, o segnali,
diversi, risulta abbastanza evidente che i modelli si vogliano poter gestire
trattino sequenze provenienti da un generico alfabeto. Il lavoro per la realizzazione 
del framework è stato organizzto in quattro fasi incrementali i cui obiettivi sono qui presentati:

\begin{enumerate}
  \item Dato un insieme di stringhe (sequenze di osservazioni) proveniente da un insieme di modelli completamente noti, determinare quale è il modello che più verosimilmente ha generato ogni stringa.
  \item Dato un insieme di stringhe proveniente da un insieme di modelli
  completamente noti e le probabilità a priori di ogni singolo modello
  determinare il modello che più verosimilmente ha generato ogni sequenza.
  \item Dato un insieme di stringhe proveniente da un insieme di modelli
  completamente noti e una stima iniziale delle loro probabilità a priori
  stimare e apprendere le loro probabilità a priori.
  \item Dato un insieme di stringhe, il numero di modelli e k modelli iniziali
  costruire i modelli che più verosimilmente hanno generato le stringhe e
  stimare le loro probabilità a priori.
\end{enumerate}

\subsection{Struttra del documento}
Il resto del documento è suddiviso come segue. Poichè il progetto  si
basa sugli Hidden Markov Models, nella seconda parte verrano introdotti
sinteticamente e verrà proposto un ambito di possibile utilizzo del framework.
Nella terza sezione si entrerà nel vivo dell'implementazione, descrivendo la
risoluzione alle fasi del progetto. 
La quarta sezione verrà utilizzata per presentare degli scenari di
utilizzo del framework per mezzo di alcuni esempi. Infine la quinta sezione
conterrà alcune considerazioni finali e gli sviluppi futuri.

\section{Strumenti teorici e finalità}

Prima di proseguire nella descrizione dello svolgimento del progetto verrà
introdotto lo strumento matematico sui cui esso si basa: gli Hidden Markov Model.
Si cercherà inoltre di chiarire le ragioni per cui si è ritenuto questo strumento
adatto alle problematiche affrontate.

\subsection{Introduzione agli Hidden Markov Model}

In base a quanto affermato nell'introduzione, l'ambito del lavoro svolto è quello
della modellizzazione di un processo reale. Tale processo produce nel tempo una
serie di output osservabili. Questi output possono essere caratterizzati come
segnali, come variabili che evolvono nel tempo. Assegnando un indice temporale
$t$ a queste variabili, il modello causale più semplice per una sequenza di dati
${Y_1, Y_2, \ldots, Y_T}$ è una \emph{catena di Markov del primo ordine} di cui
un esempio è mostrato in figura \ref{fig:firstordermarkov}.

\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=3in]{firstordermarkov.png} 
   \caption{Esempio di catena di markov del primo ordine}
   \label{fig:firstordermarkov}
\end{figure}

In un modello così costruito vale la relazione  \ref{eq:equazione1}.
 
\begin{equation}
P(Y_1, Y_2, \ldots, Y_T) = P(Y_1)P(Y_2 | Y_1) \ldots P(Y_{T} | Y_{T-1})
\label{eq:equazione1}
\end{equation}

Il termine primo ordine sta a significare che, avendo osservato la sequenza
${Y_1, Y_2, \ldots, Y_T}$, il modello farà uso solamente di $Y_{T}$ per
predirre il valore di $Y_{T+1}$\cite{zoubin}.

Si ottengono catene markoviane di ordine superiore, permettendo una dipendenza
temporale più estesa nel passato. In pratica in un modello di ordine $\tau$ il
calcolo della probabilità di emissione in un dato istante dipende dai $\tau$
istanti precedenti. In accordo con questa definizione gli stati del modello
risultano coincidenti con il valore assunto dalla particolare variabile scelta,
quindi in realtà si ha tra le mani un modello probabilistico di uno dei
``segnali'' che caratterizzano il processo, e non si possiede conoscenza sui
diversi stati in cui il processo può trovarsi.

Un Hidden Markov Model (HMM) può essere visto sia come la generalizzazione
probabilistica di un automa non deterministico a stati finiti sia come un
processo stocastico che ha una struttura sottostante di tipo markoviana a stati
finiti la quale può solo essere osservata in maniera indiretta (da qui
l'attributo hidden del nome). Come gli automi a stati finiti, gli HMM hanno un
insieme di stati connessi tramite transizioni e ogni stato può emettere, con una
determinata probabilità, un simbolo appartenente ad un alfabeto discreto e
finito. Una variante degli HMM può essere progettata per emettere simboli in fase
di transizione al posto che in corrispondenza degli stati, ma visto che si tratta
di una formulazione equivalente, questo caso non verrà contemplato. I modelli che
verranno trattati in questo framework sono del primo ordine, pertanto vale ancora
la relazione \ref{eq:equazione1}. La scelta di trattare modelli del primo ordine
non è una limitazione in quanto modelli di ordine superiore al primo possono
essere ricondotti con delle trasformazioni a modelli equivalenti di primo ordine.

In conlcusione un HMM consiste di due processi stocastici, uno racchiuso
nell'altro. Per chiarire il significato di doppio processo stocastico si riporta
un esempio. Si supponga di trovarsi in una stanza mentre, nella stanza accanto,
vengono fatti dei lanci con una moneta. Gli unici dati di cui si dispone sono
gli esiti del lancio nella forma di una sequenza di valore Testa o Croce. Tuttavia i lanci potrebbero essere effettuati non con una, ma con due monete,
di cui una truccata ed una non truccata. Non si sà nulla del processo che ha
generato tali osservazioni, che può trovarsi in due diversi stati corrispondenti
alla moneta truccata e a quella non truccata.\\
Nel caso degli Hidden Markov Model
sono essenzialmente due i tipi di parametri con cui si ha a che fare: le
probabilità di transizione tra stati e le probabilità di emissione nei diversi
stati. Più formalmente un Hidden Markov Model con $N$ stati e $M$ simboli di
output è costituito da:

\begin{itemize}
  \item L'insieme degli stati: 
 \begin{center}
 	$S = {s_1, s_2, \ldots, s_N}$
 \end{center} 
  	
  \item L'insieme dei simboli in uscita:
  \begin{center}
  	$O = {o_1, o_2, \ldots, o_M}$
  \end{center}
  
  \item La distribuzione delle transizioni tra stati, nella forma di matrice
  $A_{N\times N}$. Gli elementi $a_{ij}$ sono così definiti:
  \begin{center}
  	$a_{ij} = P(q_{t+1} = S_j | q_{t} = S_i),	1 \leq i, j \leq N$
  \end{center}
  
  \item La distribuzione dei simboli in uscita per ogni stato nella forma di
  matrice $B_{N\times M}$. Gli elementi $b_{ij}$ sono così definiti:
  \begin{center}
   	$b_{ij} = P(o_j | q_t = S_i), i \leq N j \leq M$
  \end{center} 
  
  \item La distribuzione delle probilità iniziali, nella forma di vettore 
  $\pi$ di dimensione $N$:
  \begin{center}
  	$\pi_i = P(q_1 = S_i), 1 \leq i \leq N$
  \end{center}
  	
\end{itemize}
La notazione $q_t$ sta a rappresentare lo stato all'istante $t$.

Dato un HMM sono in genere tre i problemi ai quali è di interesse fornire una
risposta:

\begin{enumerate}
  \item Data una specifica sequenza di simboli, determinare la probabilità di
  osservare quella specifica sequenza.   
  \item Dato un modello ed una specifica sequenza di simboli, determinare la
  sequenza di stati che con più probabilità l'ha generata.
  \item Data una sequenza, regolare i parametri del modello al fine di
  aumentare la verosimiglianza di tale sequenza.
\end{enumerate}

Tutti e tre i problemi sono importanti nell'ottica del progetto. In particolare
il nostro framework farà uso dei calcoli necessari a rispondere al primo
quesito, per valutare la performance di un modello, cioè la sua capacità tanto
di riconoscere, quanto di generare una particolare stringa. 

\subsection{Modellizzare un comportamento}

Come affermato nell'introduzione, una sequenza comportamentale può essere pensata
come costituita da una successione di azioni. È abbastanza evidente tuttavia che
un comportamento è generato, o meglio motivato, da un'intenzione che non
necessariamente ha un collegamento esplicito con le azioni eseguite. Volendo fare
un esempio apparatenente al mondo naturale, si potrebbe pensare ad un predatore
che come tecnica di caccia di finge morto. Tornando ad un ambito più quotidiano,
un individuo che intende penetrare un generico sistema di sicurezza di un
edificio, avrebbe tutte le intenzioni di comportarsi come qualcuno a cui
l'accesso a tale edificio è consentito. Per questo motivo possiamo pensare di
trovarci in presenza non di uno ma, di due processi: uno è
osservabile, mentre l'altro, da cui esso è dipendendente, no. È proprio la
presenza di questa duplicità che fa apparire gli hidden markov models lo
strumento ideale per rappresentare processi comportamentali.

Lo scopo di questo lavoro è la realizzazione di un framework che utilizzi un approccio non
supervisionato per la generazione di modelli a partire da sequenze di
osservazioni. Il framework deve essere pensato nella maniera più generica
possibile, in modo che risulti un vero e proprio ``kernel'' che faccia da
supporto per applicazioni di tipo diverso. L'idea di partenza è che questo
sistema riceva in ingresso un insieme di sequenze di vario genere. Con vario
genere si intende, in maniera molto astratta, che queste sequenze sono formulate
a partire da diversi alfabeti e con diverse grammatiche. Seguendo la definizione
di comportamento data nell'introduzione, l'insieme di azioni che costituisce il
repertorio dell'agente varia a seconda del contesto. Le azioni possono essere
comandi immessi in un terminale, articoli aquistati su un sito di e-commerce o
azioni fisiche vere e proprie. Tale insieme di azioni può essere codificato come
si ritiene più opportuno. Il framework, stabilito l'alfabeto, opererà per mezzo
di esso in maniera del tutto indipendente. La cosa più importante però, e molto
più attinente a questo progetto, è che le varie sequenze sono originate con una
diversa semantica e presumibilmente con un diverso scopo. Il fine che con questo
framework ci si prefigge è duplice:

%\flushleft
\begin{enumerate}
\item Estrarre dalle sequenze i o il modello che le ha prodotte, in maniera non supervisionata;
\item Fare sì che questi modelli siano utilizzabili per scopi diversi, con
l'idea che tramite essi si possano fare delle inferenze di ``alto livello''.
\end{enumerate}

\section{Implementazione del framework}

Per sviluppare il framework, si sono seguiti i quattro punti forniti come
specifiche. L'intenzione era quella di inferire l'architettura del framework in
maniera costruttiva, elaborando di volta in volta le soluzioni ai problemi
incontrati. Nel seguito forniamo la descrizione del progetto suddivisa nei
quattro punti di cui è composto più una fase preliminare di organizzazione e
generazione dei dati.

\subsection{Fase preliminare}
Prima di poter affrontare la risoluzione di ognuno dei quattro punti si sono
definiti degli strumenti per poter generare dei modelli in maniera parzialmente
casuale così da poter in seguito generare delle sequenze di osservazioni su cui
lavorare nelle fasi successive. Cuore di questa fase è stato lo sviluppo di una
classe per la generazione di densità di probabilità con determinate
caratteristiche. Quello che interessava poter specificare in un insieme di
distribuzioni di probabilià aera:

\begin{itemize}
  \item Il numero di distribuzioni dell'insieme
  \item Il numero di simboli per ogni densità
  \item Il numero di simboli con probabilità nulla per ogni densità
  \item Il numero di sovrapposizioni tra varie distribuzioni  
\end{itemize}
Per numero di sovrapposizioni si intende quanti simboli possono avere la stessa
probabilità tra distirbuzioni diverse. Inoltre si è deciso di non sovrapporre
i simboli con densità nulla nella scelta delle sovrapposizioni. In figura
\ref{fig:density_generator} si può vedere un possibile risultato avendo
impostato il numero di simboli a 5, il numero di densità a 2 e il numero di
zeri e sovrapposizioni entrambi a 1 (ovviamente il simbolo sovrapposto è $E$
poichè nelle due distribuzioni assume lo stesso valore di probabilità).

\begin{figure}[h] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=4in]{density_generator.png} 
   \caption{Possibile risultato di una esecuzione del generatore di probabilit\'a}
   \label{fig:density_generator}
\end{figure}

Grazie a questo strumento implementato in una classe chiamata \emph{DensityGen}
sono stati generati quattro modelli in maniera casuale tramite il codice mostrato
in figura \ref{fig:generate_models} avendo specificato solo l'alfabeto comune a
tutti i modelli. Il metodo \emph{generate} della classe \emph{DensityGen} riceve
in ingresso quattro parametri che sono gli stessi quattro elencati sopra.

\begin{figure}[h] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=5in]{generate_models.png} 
   \caption{Codice per la generazione casuale di modelli}
   \label{fig:generate_models}
\end{figure}

Per la documentazione del metodo createModel e i parametri che riceve in
ingresso, come per la documentazione dei metodi della classe \emph{DensityGen} si
faccia riferimento al manuale allegato a questo documento (prodotto per mezzo di
Doxygen) in cui viene presentata la documentazione riferita al codice scritto.
% Una volta generati i modelli si è passati a generare delle sequenze di
% emissioni da ogni modello. In questa fase sono stati generati due files contenenti le emissioni secondo due
% principi: in un primo file sono state generate uno stesso numero di stringhe per
% ogni modello mentre in un secondo file sono state generate un numero $n$ di
% stringhe ripartite su ogni modello in base alla loro probabità a priori. I due
% files sono stati chiamati rispettivamente \emph{sequencesStep1.txt} e
% \emph{sequencesStep2.txt} e verranno utilizzati nelle fasi successive del
% progetto.


\subsection{Prima fase}


Nella prima fase del progetto, si è cominciato a delineare l'architettura del
framework, basandosi sulle prime funzionalità che questi avrebbe dovuto fornire.
In questa fase, dato un insieme di stringhe e l'insieme di modelli noti si deve
determinare quale modello ha, con probabilità più alta, generato ogni stringa.
Per effettuare questa valutazione ci si è avvalsi della libreria GHMM che
permette di creare dei modelli markoviani nascosti, specificandone i parametri,
e di effettuare su di essi determinate operazioni. I parametri specificabili per
ogni modello sono:

\begin{itemize}
  \item L'alfabeto delle osservazioni
  \item Una distribuzione delle osservazioni (discreta o continua)
  \item Matrice delle transizioni tra stati
  \item Matrice delle osservazioni generabili da ogni stato
  \item Un vettore di probabilità che associa ad ogni stato la probabilità che quello sia il primo stato del modello.
\end{itemize}

Una volta caricati nel framework i modelli generati nella fase preliminare si è
valutata la log-verosimiglianza per ogni stringa e per ogni modello. La
verosimiglianza $L$ è un'indicatore di quanto probabilmente una stringa è stata
generata da un modello e la log-verosimiglianza è semplicemente $log(L)$. Dato un
modello $M$ e una sequenza $\sigma$ la verosimiglianza è data dalla probabilità P
che il modello abbia generato la stringa $\sigma$. Più formalmente data una
stringa $\sigma$ composta da $n$ simboli $ s_{1}...s_{n} $ e un modello M la
verosimiglianza della stringa riferita al modello è data da:
\begin{equation}
L(\sigma)=P(\sigma\mid M)=\sum_{\forall percorso} P(s_1\mid q_0)P(q_0 \rightarrow q_1)P(s_2\mid q_1)P(q_1 \rightarrow q_2)...p(s_n \mid q_n)
\label{eq:equazione2}
\end{equation}
Dove con per "percorso" si intende ogni possibile percorso che può generare la sequenza $\sigma$, con $P(s_i\mid q_j)$ si indende la probabilità di generare il simbolo $s_i$ nello stato $q_j$ e con $ P(q_j \rightarrow q_i)$ si intende la probabilità di andare nello stato $q_i$ essendo nello stato $q_j$.\\

La libreria ghmm permette di calcolare la log-verosimiglianza di una stringa
riferita ad un modello. Grazie a questo la prima fase del progetto è stata
realizzate semplicemente controllando che il modello più probabile secondo la
log-verosimiglianza fosse effettivamente il modello che aveva generato la
sequenza.

\subsection{Seconda fase}
In questa fase l'obiettivo è trovare quali modelli hanno generato con più
probabilità, o anche più verosimilmente, un insieme di stringhe
avendo a disposizione tutte le stringe, tutti i modelli e, a differenza della
fase precedente, anche le probabilità a priori di ogni modello.

Per calcolare questo si usa la formula \ref{eq:equazione3} che è semplicemente la
\ref{eq:equazione2} filtrata per la probabilità a priori del modello M.
\begin{eqnarray}
\nonumber L(\sigma) = P(\sigma\mid M)= \\
\nonumber =\sum_{\forall percorso} P_{apriori}(M)P(s_1\mid q_0)P(q_0 \rightarrow q_1)P(s_2\mid q_1)P(q_1 \rightarrow q_2)...p(s_n \mid q_n) = \\
= P_{apriori}(M)\sum_{\forall percorso}P(s_1\mid q_0)P(q_0 \rightarrow q_1)P(s_2\mid q_1)P(q_1 \rightarrow q_2)...p(s_n \mid q_n)
\label{eq:equazione3}
\end{eqnarray}
Riportando tutto in termini di log-verosimiglianza si sommerà al risultato della
fase precedente il logaritmo della probabilità a priori del modello considerato
ottenendo così il risultato espresso in \ref{eq:equazione3}.
La valutazione poi per ogni modello verrà effettuata in maniera analoga alla prima fase.

\subsection{Terza fase}
Nella terza fase si è cercato di stimare le probabilità a priori di ogni modello
avendo a disposizione i modelli e le sequenze generate. L'idea di fondo in questa
fase è quella di contare quante volte ogni modello riconosce delle sequenze e poi
di ritrasformare le frequenze relative di ogni modello in probabilità. La stima
delle probabilità è un procedimento iterativo e incrementale che viene effettuato
dopo ogni riconoscimento di una sequenza e non una sola volta alla fine di tutte
le sequenze. Per questo motivo, per uniformare l'input ed evitare che le
probabilità di un modello vengano incrementate troppo a sfavore della probabilità
degli altri, le sequenze vengono mischiate prima di essere passate al framework. Inoltre per evitare che un numero
troppo basso di modelli introduca un rumore elevato nella stima delle
probabilità, le frequenze iniziali di ogni modello non sono poste a zero ma ad un
numero che può essere impostato a discrezione dell'utente. Per questa fase sono
state ovviamente utilizzate le sequenze ripartite per ogni modello in base alle
probabilità a priori perchè la probabilità a priori di ogni modello è stimata
direttamente dal numero di sequenze che ogni modello riconosce e quindi per lo
stesso motivo il numero delle sequenze deve rispecchiare le probabilità a priori.
\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering
   \includegraphics[width=4in]{step3.png} 
   \caption{Codice per l'apprendimento delle probabilità a priori}
   \label{fig:step3}
\end{figure}


In figura \ref{fig:step3} si può vedere come viene utilizzato il framework per la
stima delle probabilità. Alla linea 25 vengono inzializzate le probabilità a
priori di ogni modello a $5$. Alle linee dalla 32 alla 37 viene mischiato e
uniformato l'input. Il metodo \emph{learnApriori} riceve in ingresso una sequenza
e riadatta le frequenze del modello che più verosimilmente l'ha generata. Infine
il metodo \emph{finalizeApriori} alla linea 42 viene utilizzato per ritrasformare
le frequenze di ogni modello in probabilità.

\subsection{Quarta fase}
In questa fase si è cercato di ottenere un numero $n$ di modelli che possano generare 
con buona probabilità, tenendo conto anche delle loro probabilità a priori, ogni
sequenza in esame. Per ottenere questo insieme di modelli si sono seguite le
indicazioni trovate in \cite{stolcke93hidden} partendo da un insieme molto vasto
di modelli e unendo coppie di stati fino a quando il risultato ottenuto non fosse
stato soddisfacente. In seguito si vedrà come valutare un insieme "soddisfacente"
di modelli.\\
La prima parte di questa fase consiste, quindi, nel generare un grande
insieme di modelli che possono generare tutte le sequenze. Questo viene fatto
creando per ogni sequenza di osservazioni il modello che può generare con
probabilità 1 quella sequenza. In pratica i modelli avranno tutti la topologia di
una catena, ogni stato potrà emettere con probabilità 1 solo un simbolo e le
probabilità a priori saranno uguali per tutti i modelli. L'insieme di modelli
così generati è il meno generico possibile in quanto ogni modello può generare
una sola sequenza di simboli. A partire dai modelli generati si esegue l'unione
di coppie di stati e per fare ciò sono stati definiti due metodi diversi nel
framework per l'unione in due modelli distinti o nello stesso modello
rispettivamente chiamati \emph{mergeModels} e \emph{mergeStates}. La scelta degli
stati da unire viene fatta in base al valore ritornato da una funzione di
valutazione relativa ad ogni possibile fusione di coppia di stati presenti nel
modello, ovvero dopo aver provato tutte le possibili coppie da unire, si valuta
se vi è stato un miglioramento e, se vi è stato, si uniscono gli stati che hanno
portato a questo miglioramento. La funzione di valutazione scelta nel framework
valuta per ogni modello l'opposto della log-verosimiglianza calcolata per le
sequenze che può generare e le filtra per la probabilità a priori di ogni
modello. L'opposto della log-verosimiglianza assume la forma di una funzione di
errore avendo come minimo zero quando la sequenza viene generata con probablilità
uno dal modello in analisi.
La terminazione della fase di fusione dipende da
alcuni parametri specificabili dall'utente, ma non può comunque andare oltre
al caso in cui sia presente un solo modello composto da due stati o due modelli
da un singolo stato. I parametri specificabili sono:
\begin{itemize}
  \item Il numero minimo di modelli sotto il quale non si vuole scendere con la
  generalizzazione.
  \item L'errore massimo tollerabile alla fine di un passo di fusione.
  \item Il numero massimo di incrementi dell'errore che si è disposti ad
  accettare
\end{itemize}


%Dopo aver inserito nel framework i modelli che hanno generato le sequense, queste sono state mischiate e  si sono mischiate 

%generare il simbolo $s_1$ essendo nello stat $q_0$
%Il primo requisito è che i modelli  abbiamo come alfabeto di emissione un insieme di 15 simboli, la cui distribuzione deve essere parzialmente sovrapposta. Secondo la nostra interpretazione per alafabeto parzialmente sovrapposto si instende che in un singolo modello ogni stato può emettere simboli con probabilità identica a quella di altri stati e simboli con probabilità nulla.
   
%In questa fase richiediamo al framework che, dato un insieme di modelli ed una stringa dell'alfabeto, ci dica quale di questi modelli ha generato più verosimilmente quella stringa. 
%Vogliamo cioè calcolare per ogni modello, la probabilità che quel modello abbia generato una stringa, cioè ci occore al soluzione al primo problema così come descritto nel tutorial di Rabiner.

\section{Test del framework}

In questa sezione vengono presentati i risultati sperimentali ottenuti
utilizzando il framework. La suddivisione di questa sezione segue quella della
sezione precedente. 

\subsection{Prima Fase}

Per valutare il funzionamento del framework relativamente al primo requisito,
sono state contate quante sequenze vengono associate correttamente al modello che
le ha generate. Come risultato sperimentale vengono mostrate le percentuali di associazioni errate utilizzando un numero diverso di modelli.
% e un numero diverso di sequenze.
I modelli utilizzati vengono generati con parametri scelti in modo casuale e ad
ogni modello viene fatto generare uno stesso numero di sequenze fino ad un totale
di 1000. Su tali sequenze, di cui quindi è nota la provenienza, viene applicato
il metodo \emph{mostLikelyModel} e si conta il numero di volte che il modello
stimato corrisponde al modello effettivo. Il tutto viene ripetuto 10 volte per
ogni gruppo di modelli.
 Dal grafico in figura \ref{fig:test_step1} è
possibile notare che l'aumentare del numero di modelli produce un lieve
incremento nelle difficoltà di riconoscimento delle sequenze infatti l'errore è
più alto all'aumentare del numero di modelli. 

\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=5in]{test_step1.png}
   \caption{Andamento dell'errore all'aumentare dei modelli}
   \label{fig:test_step1}
\end{figure}

Il picco nel grafico riguardante un gruppo di 5 modelli può essere
tranquillamente considerato rumore. Infatti generando a caso tutti i modelli è
plausibile che due o più siamo piuttosto simili e che quindi le sequenze generate
da un modello vengano erroneamente associate ad un altro.
 
% grafico



\subsection{Seconda Fase}

La valutazione del secondo requisito è molto simile a quella precedente. Ancora
una volta vengono usati dei modelli generati con parametri scelti in modo casuale
e ancora una volta si usano per dieci volte gruppi di 1000 sequenze. Dato il
numero di modelli, tramite la classe \emph{DensityGen}, viene creata una
distribuzione che rappresenta la probabilità a priori per ogni modello.
In base a queste probabilità vengono scelti i modelli ai quali si fanno genereare
delle sequenze. Come nel test precedente, si valuta il numero di associazioni
corrette indivuate dal framework. Si mostrano, in figura
\ref{fig:test_step2}, i risultati del test al variare del numero di modelli .\\
% e al variare della distribuzione. Non sarebbe interessante fare un test con
% sequenze generate da modelli presi completamente a caso?
\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=5in]{test_step2.png}
   \caption{Andamento dell'errore all'aumentare dei modelli}
   \label{fig:test_step2}
\end{figure}
Anche questa in questa fase, come nella precedente, si nota che l'aumentare del
numero di modelli rende più difficoltoso il riconoscimento anche se le differenze
tra gli errori commessi nei tre gruppi sono minori grazie alle probabilità a
priori di ogni modello.

\subsection{Terza Fase}

L'obiettivo del test relativo al terzo requisito è verificare che il framework
inferisca delle probabilità a priori consistenti con il processo che si sta
analizzando. Come nella prima fase si parte da un insieme di modelli con
associata una fissata probabilità a priori in base alla quale vengono generate
delle sequenze di osservazioni. Il test consiste nel verificare quanto le
probabilità a priori apprese per mezzo del framework a partire dalle sequenze
fornitegli siano aderenti a quelle con cui le stesse sequenze sono state
generate. Nei risultati mostriamo le differenze tra le probabilità a priori note
e quelle apprese dal framework nel caso vengano utilizzati 2 (figura
\ref{fig:test_step3a}), 5 (figura \ref{fig:test_step3b}) o 10 modelli (figura
\ref{fig:test_step3c}). Il test viene ripetuto 10 volte per ogni gruppo di
modelli e nei grafici sottostanti si trovano in ascissa l'esecuzione corrente
mentre in ordinata si trovano le differenze tra le probabilità a priori stimate e
quelle reali. 

\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=5in]{test_step3a.png}
   \caption{Differenze tra probabilità a priori stimate e reali per 2 modelli}
   \label{fig:test_step3a}
\end{figure}
\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=5in]{test_step3b.png}
   \caption{Differenze tra probabilità a priori stimate e reali per 5 modelli}
   \label{fig:test_step3b}
\end{figure}
\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=5in]{test_step3c.png}
   \caption{Differenze tra probabilità a priori stimate e reali per 10 modelli}
   \label{fig:test_step3c}
\end{figure}

Come si può notare i risultati sono buoni in quanto l'errore massimo che si
compie non supera in nessun caso il 4\%.

\subsection{Quarta Fase}

L'ultimo test serve a valutare la capacità del framework di apprendere ed operare
generalizzazioni su dei modelli a partire da un insieme di sequenze. Il test
consiste nel fornire al metodo \emph{learn} un set di sequenze generate casualmente e
variando i parametri che regolano l'apprendimento si cerca di apprendere il modello che le ha generate.
Dando come input al framework un insieme di stringhe appartenenti alla grammatica $(ab)^{+}$ il risultato ottenuto è quello presentato in figura \ref{fig:test_step4a}.\\

\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=2in]{test_step4a.png}
   \caption{Modello risultante da grammatica $(ab)^{+}$}
   \label{fig:test_step4a}
\end{figure}

In questo modello lo stato inziale è lo stato 0 con probabilità $1$ e le
transizioni da $0$ a $1$ e da $1$ a $0$ hanno probabilità $1$. Le probabilità di
emettere $b$ nello stato $0$ e di emettere $a$ nello stato $1$ sono state omesse
in quanto $0$ entrambe.

Un ulteriore test è stato effettuato con un insieme di stringhe generate dalla
grammatica $a^+b^*c^+$ e il risultato è mostrato in figura \ref{fig:test_step4b}
dove lo stato iniziale è lo stato $3$. 

\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=2.5in]{test_step4b.png}
   \caption{Modello risultante da grammatica $a^+b^*c^+$}
   \label{fig:test_step4b}
\end{figure}



\begin{figure}[h!tbp] %  figure placement: here, top, bottom, or page
   \centering \includegraphics[width=3in]{test_step4c.png}
   \caption{Modello ottimale per la grammatica $a^+b^*c^+$}
   \label{fig:test_step4c}
\end{figure}

Benchè il risultato non sia quello ottimale mostrato in figura
\ref{fig:test_step4c} si può comunque osservare come il modello generato non si
discosti più di tanto da quello effettivo facendo presupporre che con
l'inserimento di parametri diversi si possa comunque raggiungere la soluzione
mostrata in figura \ref{fig:test_step4c}. Purtroppo per numerose sequenze di
osservazioni di lunghezza elevata l'algoritmo di apprendimento non è in grado di
fornire un risultato in tempi brevi perchè risulta essere piuttosto sensibile al
numero di osservazioni fornite.

\section{Conclusioni e Sviluppi futuri}
In questo documento abbiamo presentato le fasi di sviluppo di un framework per
gestione e apprendimento di sequenze di osservazioni. Lo scopo di tale framework
è quello di essere utilizzato per classificare e apprendere processi di tipo
comportamentale, al fine di creare modelli che possano essere utilizzati in
diversi ambiti di applicazione dell'intelligenza artificiale. Abbiamo messo in
evidenza come, benchè i risultati ottenuti nelle prime tre fasi di test siano
promettenti, la quarta fase, relativa all'apprendimento di modelli, è fortemente
vittima dell'esplosione esonenziale degli stati durante la fase di ricerca delle
migliori candidate per la fusione. Per questo motivo, sviluppi futuri di questo
lavoro riguardano senza dubbio il miglioramento della procedura di selezione di
due stati da fondere, ad esempio tramite l'impiego di appropriate euristiche o
algoritmi genetici.

%Before the end of the document
\newpage
\bibliography{doc}
\bibliographystyle{plain}
\end{document}